package com.guiwu.jjj.leecode.easy;

import sun.java2d.pipe.AAShapePipe;

import javax.print.DocFlavor;
import javax.swing.plaf.basic.BasicInternalFrameTitlePane;
import java.util.*;
import java.util.stream.Collectors;

/**
 * 力扣练习题答案
 *
 * @author jiangjinjian
 * @date 2023/3/14
 * @description
 */
public class SolutionTow {

    /**
     * 剑指 Offer 42. 连续子数组的最大和
     *
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        int[] count = new int[nums.length];
        count[0] = nums[0];
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            count[i] = Math.max(count[i - 1] + nums[i], nums[i]);
            max = Math.max(count[i], max);
        }
        return max;
    }

    /**
     * 剑指 Offer II 003. 前 n 个数字二进制中 1 的个数
     *
     * @param n
     * @return
     */
    public int[] countBits(int n) {
        int[] nums = new int[n + 1];
        nums[0] = 0;
        int x = 2;
        for (int i = 1; i <= n; i++) {
            nums[i] = Integer.bitCount(i);
        }
        return nums;
    }

    /**
     * 剑指 Offer II 088. 爬楼梯的最少成本
     *
     * @param cost
     * @return
     */
    public int minCostClimbingStairs(int[] cost) {
        int[] count = new int[cost.length + 1];
        count[1] = 0;
        for (int i = 2; i <= cost.length; i++) {
            count[i] = Math.min(count[i - 1] + cost[i - 1],
                    cost[i - 2] + count[i - 2]);
        }
        return count[cost.length];
    }


    /**
     * 面试题 05.03. 翻转数位
     *
     * @param num
     * @return
     */
    public int reverseBits(int num) {
        if (num == 0) return 1;
        int res = 1, insert = 0, curr = 0;
        for (int i = 0; i < 32; i++) {
            //不为零说明该位为1
            if ((num & (1 << i)) != 0) {
                curr += 1;
                insert += 1;
            } else {
                insert = curr + 1;
                curr = 0;
            }
            res = Math.max(res, insert);
        }
        return res;
    }

    /**
     * 面试题 08.01. 三步问题
     *
     * @param n
     * @return
     */
    public int waysToStep(int n) {
        if (n <= 2) return n;
        long[] nums = new long[n + 1];
        nums[1] = 1;
        nums[2] = 2;
        nums[3] = 4;
        long temp = 0;
        for (int i = 4; i <= n; i++) {
            temp = nums[i - 1] + nums[i - 2] + nums[i - 3];
            nums[i] = temp % 1000000007;
        }
        return (int) nums[n];
    }

    /**
     * 面试题 16.17. 连续数列
     *
     * @param nums
     * @return
     */
    public int maxSubArray1(int[] nums) {
        if (nums.length == 0) return 0;
        int[] count = new int[nums.length];
        count[0] = nums[0];
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            count[i] = Math.max(count[i - 1] + nums[i], nums[i]);
            max = Math.max(max, count[i]);
        }
        return max;
    }

    /**
     * 面试题 17.16. 按摩师
     *
     * @param nums
     * @return
     */
    public int massage(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        int[] count = new int[nums.length];
        count[0] = nums[0];
        count[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            count[i] = Math.max(count[i - 2] + nums[i],
                    count[i - 1]);
        }
        return count[nums.length - 1];
    }

    private static Map<Character, Integer> map = new HashMap<>();

    static {
        map.put('I', 1);
        map.put('v', 5);
        map.put('X', 10);
        map.put('L', 50);
        map.put('C', 100);
        map.put('D', 500);
        map.put('M', 1000);
    }

    /**
     * 13. 罗马数字转整数
     *
     * @param s
     * @return
     */
    public int romanToInt(String s) {
        if (s.length() == 1) return map.get(s.charAt(0));
        int res = 0, temp = map.get(s.charAt(0));
        for (int i = 1; i < s.length(); i++) {
            Integer curr = map.get(s.charAt(i));
            Integer last = map.get(s.charAt(i - 1));
            if (curr > last) {
                res += curr - temp;
                temp = 0;
            } else if (curr == last) {
                temp += curr;
            } else {
                res += temp;
                temp = curr;
            }
        }
        res += temp;
        return res;
    }

    /**
     * 67. 二进制求和
     *
     * @param a
     * @param b
     * @return
     */
    public String addBinary(String a, String b) {
        if (a.length() == 0) return b;
        if (b.length() == 0) return a;
        int n = a.length() - 1, m = b.length() - 1;
        String res = "";
        int ten = 0;
        while (n >= 0 && m >= 0) {
            int ac = a.charAt(n--) - 48;
            int bc = b.charAt(m--) - 48;
            res = (ac + bc + ten) % 2 + res;
            ten = (ac + bc + ten) / 2;
        }
        while (n >= 0) {
            int ac = a.charAt(n--) - 48;
            res = (ac + ten) % 2 + res;
            ten = (ac + ten) / 2;
        }
        while (m >= 0) {
            int bc = b.charAt(m--) - 48;
            res = (bc + ten) % 2 + res;
            ten = (bc + ten) / 2;
        }
        if (ten != 0)
            res = ten + res;
        return res;
    }

    /**
     * 14. 最长公共前缀
     *
     * @param strs
     * @return
     */
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) return "";
        if (strs.length == 1) return strs[0];
        int firstLength = strs[0].length();
        int start = 0, length = Integer.MAX_VALUE, temp = 0;
        for (int i = 1; i < strs.length; i++) {
            String str = strs[i];
            for (int j = 0; j < str.length(); j++) {
                if (j < firstLength && str.charAt(j) == strs[0].charAt(j)) {
                    temp++;
                } else {
                    break;
                }
            }
            if (length >= temp) {
                length = temp;
                temp = 0;
            }
        }
        if (length == 0) return "";
        return strs[0].substring(start, length);
    }


    /**
     * 58. 最后一个单词的长度
     *
     * @param s
     * @return
     */
    public int lengthOfLastWord(String s) {
        if (s.length() == 0) return 0;
        String[] strings = s.split(" ");
        String last = strings[strings.length - 1];
        return last.trim().length();
    }

    /**
     * 125. 验证回文串
     *
     * @param s
     * @return
     */
    public boolean isPalindrome(String s) {
        if (s.length() < 2) return true;
        StringBuilder strBuilder = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c >= 'a' && c <= 'z') {
                strBuilder.append(c);
            } else if (c + 32 >= 'a' && c + 32 <= 'z') {
                strBuilder.append((char) (c + 32));
            } else if (c >= '0' && c <= '9') {
                strBuilder.append(c);
            }
        }
        String str = strBuilder.toString();
        System.out.println(str);
        for (int i = 0, j = str.length() - 1; i < str.length() / 2; i++, j--) {
            if (str.charAt(i) != str.charAt(j))
                return false;
        }
        return true;
    }

    private static Map<Integer, String> map26 = new HashMap<>();

    static {
        map26.put(1, "A");
        map26.put(2, "B");
        map26.put(3, "C");
        map26.put(4, "D");
        map26.put(5, "E");
        map26.put(6, "F");
        map26.put(7, "G");
        map26.put(8, "H");
        map26.put(9, "I");
        map26.put(10, "J");
        map26.put(11, "K");
        map26.put(12, "L");
        map26.put(13, "M");
        map26.put(14, "N");
        map26.put(15, "O");
        map26.put(16, "P");
        map26.put(17, "Q");
        map26.put(18, "R");
        map26.put(19, "S");
        map26.put(20, "T");
        map26.put(21, "U");
        map26.put(22, "V");
        map26.put(23, "W");
        map26.put(24, "X");
        map26.put(25, "Y");
        map26.put(26, "Z");
    }

    /**
     * 168. Excel表列名称
     *
     * @param columnNumber
     * @return
     */
    public String convertToTitle(int columnNumber) {
        if (columnNumber < 27) return map26.get(columnNumber);
        String res = "";
        while (columnNumber / 26 != 0) {
            int num = columnNumber % 26;
            if (num == 0) {
                columnNumber -= 1;
                num = 26;
            }
            res = map26.get(num) + res;
            columnNumber /= 26;
        }
        if (columnNumber != 0)
            res = map26.get(columnNumber) + res;
        return res;
    }

    /**
     * 171. Excel 表列序号
     *
     * @param columnTitle
     * @return
     */
    public int titleToNumber(String columnTitle) {
        Map<String, Integer> map = map26.entrySet().stream()
                .collect(Collectors.toMap(Map.Entry::getValue, Map.Entry::getKey));
        int len = columnTitle.length();
        int index = 0;
        int res = 0;
        while (index < len) {
            String c = String.valueOf(columnTitle.charAt(index));
            int curr = map.get(c);
            res += Math.pow(26, len - index++ - 1) * curr;
        }
        return res;
    }

    /**
     * 205. 同构字符串
     *
     * @param s
     * @param t
     * @return
     */
    public boolean isIsomorphic(String s, String t) {
        if (s.length() == 0 || t.length() == 0 || s.length() != t.length()) return false;
        Map<Character, Character> map = new HashMap<>();
        int len = s.length();
        StringBuilder sBuilder = new StringBuilder();
        List<Character> characterList = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            char tc = t.charAt(i);
            if (!map.containsKey(c) && !characterList.contains(tc)) {
                map.put(c, tc);
                characterList.add(tc);
            }
            sBuilder.append(map.get(c));
        }
        return sBuilder.toString().equals(t);
    }


    /**
     * @param s
     * @param t
     * @return
     */
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length())
            return false;
        int[] alpha = new int[26];
        for (int i = 0; i < s.length(); i++) {
            alpha[s.charAt(i) - 'a']++;
            alpha[t.charAt(i) - 'a']--;
        }
        for (int i = 0; i < 26; i++)
            if (alpha[i] != 0)
                return false;
        return true;
    }

    /**
     * 旋转数组
     *
     * @param nums
     * @param k
     */
    public void rotate(int[] nums, int k) {
        if (nums.length == 0) return;
        int len = nums.length;
        if (k % len == 0) return;
        int startIndex = len - k % len;
        int shortLen = startIndex;
        int[] newNums = new int[len];
        int index = 0;
        while (index < k % len)
            newNums[index++] = nums[startIndex++];
        int j = 0;
        while (index < len && j < shortLen) {
            newNums[index++] = nums[j++];
        }
        for (int i = 0; i < len; i++) {
            nums[i] = newNums[i];
        }
    }

    /**
     * 删除排序数组中的重复项
     *
     * @param nums
     * @return
     */
    public int removeDuplicates(int[] nums) {
        if (nums.length < 2) return nums.length;
        int slow = 0, fast = 1;
        while (fast < nums.length) {
            if (nums[slow] != nums[fast]) {
                slow++;
                nums[slow] = nums[fast];
            }
            fast++;
        }
        return slow + 1;
    }

    /**
     * 存在重复元素
     *
     * @param nums
     * @return
     */
    public boolean containsDuplicate(int[] nums) {
        if (nums.length < 2) return false;
        Arrays.sort(nums);
        int left = 0, right = 1;
        while (right < nums.length) {
            if (nums[left++] == nums[right++])
                return true;
        }
        return false;
    }

    /**
     * 只出现一次的数字
     *
     * @param nums
     * @return
     */
    public int singleNumber(int[] nums) {
        if (nums.length == 1) return nums[0];
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            res ^= nums[i];
        }
        return res;
    }

    /**
     * 删除字符串中出现次数最少的字符
     *
     * @param s
     * @return
     */
    public static String delMinChar(String s) {
        if (s.length() < 3) return s;
        int[] nums = new int[26];
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            nums[c - 'a']++;
        }
        int min = Arrays.stream(nums)
                .filter(num -> num != 0)
                .min().getAsInt();
        for (int i = 0; i < 26; i++) {
            if (nums[i] == min) {
                char d = (char) (i + 'a');
                String replace = String.valueOf(d);
                s = s.replace(replace, "");
            }
        }
        return s;
    }

    /**
     * 数组排序
     *
     * @param nums
     * @param rule
     */
    public static void sortNums(int[] nums, int rule) {
        Arrays.sort(nums);
        if (rule == 1) {
            int i = 0, j = nums.length - 1;
            while (i < j) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                i++;
                j--;
            }
        }
    }

    /**
     * 移除元素
     *
     * @param nums
     * @param val
     * @return
     */
    public int removeElement(int[] nums, int val) {
        if (nums.length == 0) return 0;
        if (nums.length == 1 && nums[0] == val) return 0;
        int left = 0, right = 0;
        while (right < nums.length) {
            if (nums[right] != val) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++;
            }
            right++;
        }
        return left;
    }


    /**
     * 35. 搜索插入位置
     *
     * @param nums
     * @param target
     * @return
     */
    public int searchInsert(int[] nums, int target) {
        if (nums.length == 0) return 0;
        int i = 0, j = nums.length - 1;
        while (i <= j) {
            int mid = (j + i) / 2;
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] > target)
                j = mid - 1;
            else i = mid + 1;
        }
        if (i == nums.length) return i;
        if (j == -1) return 0;
        return nums[j] < target ? i : j;
    }

    /**
     * 加一
     *
     * @param digits
     * @return
     */
    public int[] plusOne(int[] digits) {
        int i = digits.length - 1;
        int ten = 0;
        int temp = digits[i] + 1;
        digits[i--] = (temp + ten) % 10;
        ten = temp / 10;
        while (i >= 0) {
            int temp1 = (digits[i] + ten);
            digits[i--] = temp1 % 10;
            ten = temp1 / 10;
        }
        if (ten == 0) return digits;
        else {
            int[] nums = new int[digits.length + 1];
            nums[0] = ten;
            for (int j = 1; j < nums.length; j++) {
                nums[j] = digits[j - 1];
            }
            return nums;
        }
    }

    /**
     * 合并两个有序数组
     *
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if (m != 0 && n == 0) return;
        if (m == 0 && n != 0) {
            for (int i = 0; i < n; i++)
                nums1[i] = nums2[i];
        }
        int index = 0;
        for (int i = m; i < m + n; i++) {
            nums1[m] = nums2[index++];
        }
        Arrays.sort(nums1);
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 108. 将有序数组转换为二叉搜索树
     *
     * @param nums
     * @return
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        return null;
    }


    /**
     * 寻找配对
     *
     * @return
     */
    public static boolean findCouple(List<Integer> even,
                                     int index, List<Integer> odd,
                                     List<Integer> couple, List<Integer> ignore) {
        for (int i = 0; i < odd.size(); i++) {
            int n = even.get(index) + odd.get(i);
            if (isPrime(n) && ignore.indexOf(i) == -1) {
                ignore.add(i);
                int theIndex = couple.indexOf(i);
                if (theIndex == -1 || findCouple(even, theIndex, odd, couple, ignore)) {
                    couple.set(index, i);
                    return true;
                }
            }
        }
        return false;
    }


    /**
     * 是否是素数
     *
     * @param n
     * @return
     */
    public static boolean isPrime(int n) {
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) return false;
        }
        return true;
    }


    public static int find(int n) {
        int i = n/2, j = n - i;
        while (!isPrime(i) || !isPrime(j)) {
            i++;
            j--;
        }
        return j;
    }


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        int res = find(num);
        System.out.println(res);
        System.out.println(num - res);
    }
}
